package org.chnxi.study.datastructrues.sort;

import java.util.Arrays;

/**
 * 选择排序，从低到高进行排序
 */
public class SelectSorting {

    public static void main(String[] args) {
        //步骤拆解
        System.out.println("使用步骤拆解方式：");
        int[] arr = new int[]{101, 34, 119, 1};
        selectSortByStep(arr);

        //合并步骤
        System.out.println("使用合并步骤方式：");
        int[] arr2 = new int[]{101, 34, 119, 1};
        selectSort(arr2);
        System.out.println("排序后："+Arrays.toString(arr2));

        System.out.println("测试大量数据的执行耗时：");
        int[] randomArr = new int[80000];
        for (int i =0; i<80000; i++){
            randomArr[i] = (int) (Math.random()*80000);
        }

        long start = System.currentTimeMillis();
        selectSort(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));
    }

    /**
     * 采用逐步推导
     * @param arr
     */
    public static void selectSortByStep(int[] arr){
        int min = arr[0];
        int minIdx = 0;
        //第一轮，将最小值放到第一位
        for(int j= 0 + 1; j<arr.length ; j++){
            if(min > arr[j]){
                min = arr[j];
                minIdx = j;
            }
        }
        //将最小值放在arr[0]
        if(minIdx != 0){
            arr[minIdx] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一轮后："+ Arrays.toString(arr));

        //第二轮，将次小值放到第二位
        min = arr[1];
        minIdx = 1;
        //第一轮，将最小值放到第一位
        for(int j= 1 + 1; j<arr.length ; j++){
            if(min > arr[j]){
                min = arr[j];
                minIdx = j;
            }
        }
        //将最小值放在arr[0]
        if(minIdx!= 1){
            arr[minIdx] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮后："+ Arrays.toString(arr));

        //第三轮，将次小值放到第三位
        min = arr[2];
        minIdx = 2;
        //第一轮，将最小值放到第一位
        for(int j= 2 + 1; j<arr.length ; j++){
            if(min > arr[j]){
                min = arr[j];
                minIdx = j;
            }
        }
        //将最小值放在arr[0]
        if(minIdx!= 2){
            arr[minIdx] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮后："+ Arrays.toString(arr));

    }

    public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            int min = arr[i];
            int minIdx = i;
            //第一轮，将最小值放到第一位
            for(int j= i + 1; j<arr.length ; j++){
                if(min > arr[j]){
                    min = arr[j];
                    minIdx = j;
                }
            }
            //将最小值放在arr[0]
            if(minIdx != i){
                arr[minIdx] = arr[i];
                arr[i] = min;
            }
        }
    }
}
